package com.sourcetrip.algorithm.unionfind;

import com.sourcetrip.algorithm.abs.AbstractUnionFind;

/**
 * @author: ZhouBert
 * @date: 2021/1/5
 * @description: 并查集（以 Quick Union 的思路实现）
 * --
 * intro
 * 由于Quick Find 的效率太差，所以一般用 Quick Union 的思路。
 * --
 * 分析：
 * 1.每一个元素存的值都是父节点的地址，如果没有父节点，那就存自身的地址；
 * 这样可以构造出树，所以查找是 O(log n)
 * 2.由于 union 是按照 树的高度，所以 union 也是 O(log n)
 * --
 * 反思：
 * 上行的树结构，不要求往下遍历，即上面的节点无法找到下面的节点。
 */
public class UnionFindWithQuickUnionV0 extends AbstractUnionFind {
	/**
	 * 构建固定容量的并查集
	 * 默认初始 parents 的元素的根节点指向自身，这样表示每个元素都是独立的集合
	 *
	 * @param capacity 并查集的容量
	 */
	public UnionFindWithQuickUnionV0(int capacity) {
		super(capacity);
	}


	@Override
	public int find(int v) {
		rangeCheck(v);
		return locate(v);
	}

	/**
	 * 用 左边 去依附 右边（原理是通过根节点进行依附）
	 * 2log n
	 * --
	 * 分析：
	 * 虽然通过树进行了优化，但是极端情况下，树会退化成链表：
	 * 左边一棵树，依附右边一个节点。
	 * 所以为了保证树的合理，不能死规定“左边依附到右边”
	 * @param v1
	 * @param v2
	 */
	@Override
	public void union(int v1, int v2) {
		int s1 = locate(v1);
		int s2 = locate(v2);
		if (s1 == s2) {
			return;
		}
		parents[s1] = s2;
	}

	//region	core methods

	/**
	 * 根据 v 元素定位到根节点的位置
	 *
	 * @param v
	 * @return
	 */
	protected int locate(int v) {
		int res = v;
		while (parents[res] != res) {
			res = parents[res];
		}
		return res;
	}

	//endregion
}
